/**
 * 只能在原数组修改，不能生成新数组
*/ 
// 方法1不可用
function moveZero1 (arr: number[]): void {
  const length = arr.length
  if (length === 0) return

  let zeroLength = 0
  // O(n^2)
  for (let i = 0; i < length - zeroLength; i++) {
    if (arr[i] === 0) {
      arr.push(0)
      arr.splice(i, 1) // 本身就有O(n)
      i-- // 数组截取了一个元素，i要递减，否则连续0就会有错误
      zeroLength++ // 累加 0 的长度
    }
  }
}
/**
 * 方法2：双指针
 * 定义j指向第一个 0，i指向j后面的第一个非0
 * 交换i和j的值，继续向后移动
 * 只遍历一次，所以时间复杂度是O(n)
 */ 
function moveZero2 (arr: number[]): void {
  const length = arr.length
  if (length === 0) return

  let i
  let j = -1 // 指向第一个0
  for (i = 0; i < length; i++) {
    if (arr[i] == 0) {
      // 第一个0
      if (j < 0) {
        j = i
      }
    }
    if (arr[i] !== 0 && j >= 0) {
      // 交换
      const n = arr[i]
      arr[i] = arr[j]
      arr[j] = n
      j++
    }
  }
  
}